This invention relates to digital packet telecommunications, and more specifically to methods for minimizing packet queuing based upon automatically determined characteristics of the underlying network connection.
The TCP/IP protocol suite is employed in the Internet, a world-wide data communication network environment, and is also employed in local networks called Intranets. TCP technology intentionally omits explicit supervisory function over the rate of data transport over the various media comprising the network. While there are certain perceived advantages, this characteristic has the consequence of juxtaposing very high-speed packets and very low-speed packets in potential conflict, which results in inefficiencies. Resulting problems of latency and bandwidth constraints manifest themselves in delay, lost information and unsatisfied users.
The Transmission Control Protocol (TCP) provides a reliable session-based service for delivery of sequenced packets of information across the Internet. One method employed to provide reliability is to expect each end to acknowledge the data received from the other end. However, data segments and acknowledgments can be lost. To solve this problem, TCP sets a time-out when it sends data, so that the data unacknowledged is retransmitted. The TCP protocol must therefore manage a retransmission timer for each connection. The retransmission timer is used whenever TCP expects an acknowledgment from the other side. Upon transmitting some data, TCP tracks a retransmission time-out (RTO) value and a round trip time (RTT) for the given connection. If an acknowledgment is not received by the time the RTO expires, TCP retransmits the data using an exponentially increasing value for the RTO. This doubling is called an "exponential back-off." The RTO is computed as a linear function of the RTT, which is continuously tracked by TCP for each connection. Its value changes over time with changes in routing and network traffic load.
TCP has `flow control` mechanisms operative at the end stations only to limit the rate at which a TCP endpoint will emit data, but it does not employ explicit data rate control. The basic flow control mechanism is a `sliding window`, a time slot within an allowable window which by its sliding operation essentially limits the amount of unacknowledged transmit data that a transmitter can emit.
Another flow control mechanism is a congestion window, which is a refinement of the sliding window scheme involving a conservative expansion to make use of the full, allowable window. A component of this mechanism is sometimes referred to as `slow start`.
The sliding window flow control mechanism works in conjunction with the Retransmit Timeout Mechanism (RTO), which is a timeout to prompt a retransmission of unacknowledged data. The timeout length is based on a running average of the Round Trip Time (RTT) for acknowledgment receipt, i.e. if an acknowledgment is not received within (typically) the smoothed RTT+4*mean deviation, then packet loss is inferred and the data pending acknowledgment is retransmitted.
Problems arise in setting a default size for the window. A large window provides a method for overcoming network latency which does not arise from message serialization. In other words, it is data size invariant. Thus, it is useful when multiple packets can be en route between a server and a client with none of the corresponding messages being queued awaiting serialization at some bottleneck link in that path. The window size determines the amount of data that can be sent within the round trip time (RTT). The acknowledgment from the sending of data advances the window, enabling the transmission of the next data packet in sequence.
For example, an 8KB window requires approximately 45 milliseconds to serialize on a T1 link, having a transmission rate of 1.54 Mbps. That same window may take 8 seconds to be serialized on a link having a transmission rate of 9600 bps. At a representative RTT of 90 milliseconds, non-inclusive of message serialization time, the T1 connection will never reach more than half of its potential throughput rate because it will only be able to send packets for 45 milliseconds out of any 90 millisecond RTT period. The RTT will not increase as the window opens from one segment to 8KB. By contrast, the 9600 bps flow will begin to buffer packets as soon as the second packet is added to the window, i.e., en route awaiting acknowledgment. The RTT will increase as packets are added to the window and will approach the 8 second serialization time of the 8KB window. In fact, the majority of the window size is effectively added to RTT, and is buffered rather than being utilized to overcome network latency to achieve a maximum 9600 bps throughput rate.
The forgoing demonstrates that a fixed size window system results in inefficient use of network resources. Previous development efforts have centered about the problems of determining a network link's latency and adjusting corresponding flows accordingly in order to make more efficient use of network resources.
In a copending U.S. patent application Ser. No. 08/742,994, in the name of Robert L. Packer, entitled "Method for Explicit Data Rate Control in a Packet Communication Environment Without Data Rate Supervision," a technique for automatically scheduling TCP packets for transmission is disclosed. Furthermore, in a copending U.S. patent application Ser. No. 08/762,828, in the name of Robert L. Packer, entitled "Method for Rapid Data Rate Detection in a Packet Communication Environment Without Data Rate Supervision," a technique for automatically determining the data rate of a TCP connection is disclosed. Yet further, in a copending U.S. patent application Ser. No.08/970,693, in the name of Robert L. Packer, entitled "Method for Minimizing Unneeded Retransmission of Packets in a Packet Communication Environment Supporting a Plurality of Data Link Rates," filed November 14, 1997, a technique for reducing retransmissions of packets resulting from improperly configured default RTO parameters is described. While these patent applications teach methods for solving problems associated with scheduling transmissions, automatically determining a data flow rate on a TCP connection and determining a default RTO, respectively, there is no teaching in the prior art of methods for explicitly minimizing internal system buffering of TCP packets based upon a minimum window size.
The problem of excessive buffering manifests itself whenever a user clicks on a URL, Uniform Resource Locator, in order to bring new data into her browser, while a current page is still transferring. The system is incapable of responding to the user's request until all buffered packets are flushed from the path. Thus, no response occurs before the data already queued is transferred. Hence, the "world wide wait."
What is needed is a method for managing TCP window size in order to minimize the number of buffered packets on TCP connection based upon automatically determined characteristics of the underlying network connection.